package uebung2;

public class A2 {
	
}

class Sort {
	public static <K> void swap(SimpleCollection<K> field, int pos1, int pos2) {
		K temp = field.get(pos1);
		temp = field.get(pos1);
		field.set(pos1,field.get(pos2));
		field.set(pos2, temp);
	}

	static <K extends Comparable<K>> void quicksort(SimpleCollection<K> field) {
		quicksort_help(field, 0, field.size() - 1);
	}

	static <K extends Comparable<K>> void quicksort_help(SimpleCollection<K> field, int ileft,
			int iright) {
		final K MID = field.get((ileft + iright) / 2);
		int l = ileft;
		int r = iright;
		while (l < r) {
			while (field.get(l).compareTo(MID) < 0) {
				++l;
			}
			while (field.get(r).compareTo(MID) > 0) {
				--r;
			}
			if (l < r)
				swap(field, l++, r--);
		}
		if (ileft < r)
			quicksort_help(field, ileft, r);
		if (iright > l)
			quicksort_help(field, iright, l);
	}

	static <K extends Comparable<K>> void shellsort(SimpleCollection<K> field) {
		int iDist = 1;
		for (; iDist > 0; iDist /= 3) {
		}
		for (int i1 = iDist; i1 < field.size(); ++i1) {
			final K IVAL = field.get(i1);
			int i2 = i1;
			while (i2 >= iDist && field.get(i2 - iDist).compareTo(IVAL) > 0) {
				field.set(i2,field.get(i2 - iDist));
				i2 = i2 - iDist;
			}
			field.set(i2,IVAL);
		}
	}
	
	static <K extends Comparable<K>> void heapsort(SimpleCollection<K> field){
		
	}
}

interface SimpleCollection<T>{
	public int size();
	public void push_back(T arg);
	public void push_front (T arg);
	public T get(int i);
	public void set(int i, T arg);
	public void delete(int i);
}
